#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<string.h>



size_t my_strlen(const char* str)
{
	size_t count = 0;
	while (*str)
	{
		count++;
		str++;
	}
	return count;
}

char* my_strcpy(char* destination, const char* source)
{
	char* head = destination;
	while (*source)
	{
		*destination++ = *source++;
	}
	*destination = '\0';

	return head;
}

int my_strcmp(const char* str1, const char* str2)
{
	while (*str1 == *str2)
	{
		if (*str1 == '\0')
			return 0;
		str1++;
		str2++;
	}
	if (*str1 > *str2)
		return 1;
	else
		return -1;
}

char* my_strcat(char* destination, const char* source)
{
	char* head = destination;

	while (*destination)
		destination++;

	while (*source)
	{
		*destination++ = *source++;
	}
	*destination = '\0';

	return head;
}

char* my_strncpy(char* destination, const char* source, size_t num)
{
	char* head = destination;

	while (num && *source)
	{
		num--;
		*destination++ = *source++;
	}
	while (num--)
		*destination++ = '\0';

	return head;
}

char* my_strncat(char* destination, const char* source, size_t num)
{
	char* head = destination;

	while (*destination)
		destination++;

	while (num && *source)
	{
		num--;
		*destination++ = *source++;
	}

	return head;
}

int my_strncmp(const char* str1, const char* str2, size_t num)
{
	while (num && *str1 == *str2)
	{
		if (*str1 == '\0')
			return 0;
		str1++;
		str2++;
		num--;
		if (num == 0)
			return 0;
	}
	if (*str1 > *str2)
		return 1;
	else
		return -1;
}

//char* my_strstr(const char* str1, const char* str2)
//{
//	int len1 = strlen(str1);
//	int len2 = strlen(str2);
//	if (len2 > len1)
//		return NULL;
//
//	while (*str1)
//	{
//		if (*str1 != *str2)
//			str1++;
//		else
//		{
//			char* temp1 = str1;
//			char* temp2 = str2;
//			while (*temp2 && *temp1 == *temp2)
//			{
//				temp1++;
//				temp2++;
//			}
//			if (*temp2 == '\0')
//				return str1;
//			else
//				str1++;
//		}
//	}
//	return NULL;
//}


void GetNext(int* next, char* str)
{
	int len = strlen(str);

	next[0] = -1;
	int k = -1;
	int begin = 1;

	while (begin < len)
	{
		if (k == -1 || str[begin - 1] == str[k])
		{
			next[begin] = k + 1;
			k++;
			begin++;
		}
		else
		{
			k = next[k];
		}
	}

}

char* my_strstr(const char* str1, const char* str2)
{
	int len1 = strlen(str1);
	int len2 = strlen(str2);
	if (len2 > len1)
		return NULL;

	int* next = (int*)malloc(sizeof(int) * len2);
	GetNext(next, str2);

	int begin1 = 0;
	int begin2 = 0;
	while (begin1 < len1 && begin2 < len2)
	{
		if (str1[begin1] == str2[begin2])
		{
			begin1++;
			begin2++;
		}
		else
		{
			if (begin2 == 0)
				begin1++;
			else
				begin2 = next[begin2];
		}
	}
	if (begin2 == len2)
		return &str1[begin1 - begin2];
	else
		return NULL;

}


int main()
{
	char str1[20] = "abcdfababcde" ;
	char str2[20] = "abcde"; 
	
	printf("%s\n", my_strstr(str1, str2));


	return 0;
}

//int main()
//{
//
//	//int a = -1;
//	//if (a > sizeof(int))
//	//{
//	//	printf(">\n");
//	//}
//	//else
//	//{
//	//	printf("<\n");
//	//}
//	//if (strlen("abc") - strlen("abcdef") > 0)
//	//{
//	//	printf("SUCCESS\n");
//	//}
//	//else
//	//{
//	//	printf("ERROT\n");
//	//}
//	//return 0;
//
//	char str[] = "abcdefg";
//	int len = strlen(str);
//	pritnf("%d\n", len);
//
//	return 0;
//}

//1000 0000 0000 0000 0000 0000 0000 0011
//1111 1111 1111 1111 1111 1111 1111 1100
//11111111111111111111111111111101